class Solution {
    
    /** 快慢指针
     *  总要把快指针对应的元素赋给慢指针
     * 快指针遇到指定值则跳过
     * */ 
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex<nums.length; fastIndex++){
            // 快指针遇到指定值则跳过
            if(val != nums[fastIndex]){
                // 否则把快指针的对应元素赋给慢指针对应位置，且慢指针+1
                nums[slowIndex]=nums[fastIndex];
                slowIndex++;
            }
        }
        // 最后慢指针即为新数组的长度
        return slowIndex;
    }

    /**两头往中间夹
     * 
     */
    public int removeElement2(int[] nums, int val) {
        if (nums.length == 0)
            return 0;
        int p = 0, q = nums.length - 1;
        while (p < q) {
            while (p < q && nums[p] != val) {
                p++;
            }
            while (p < q && nums[q] == val) {
                q--;
            }
            if (p < q) {
                nums[p] = nums[q];
                p++;
                q--;
            }
        }
        if (p == q && nums[p] != val)
            return p + 1;
        return p;
    }
}